package 字符串;
//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
//
// 示例 1：
//
// 输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
//
//
// 示例 2：
//
// 输入: "cbbd"
//输出: "bb"
// Related Topics 字符串 动态规划
// 👍 2732 👎 0

public class 最长回文子串_5 {
	
	
	 public String longestPalindrome(String str) {
		    if (str == null || str.length() < 1) return "";
		 int start =0;
		 int end =0;
		 for(int i=0;i<str.length();i++) {
			 
			 int len1=expandAroundCenter(str,i,i);
			 int len2=expandAroundCenter(str,i,i+1);
			 int len =Math.max(len1, len2);
			 if(len>end-start) {
				 start=i-(len-1)/2;
				 end=i+len/2;
			 }
		 }
		 return str.substring(start, end+1);
		 
	 }

	private int expandAroundCenter(String str, int l, int r) {
		
		while(l>=0&&r<str.length()&&str.charAt(l)==str.charAt(r)){
			l--;
			r++;
		}
		
		return r-l-1;
	}



	//动态规划

	/**
	 * 特判：过滤掉空字符串的情况
	 * 初始化：
	 * 定义一个变量maxLen表示最长字符串长度，begin表示最长字符串首字符的位置；
	 * 定义一个二维动态数组dp,dp[i][j]表示从第i个字符开始到第j个字符结尾的字符串是否为回文字符串，
	 * 初始条件就是每个字符都是一个回文字符串，也就是dp[i][i] = true;
	 * 利用i,j两个指针遍历整个字符串，填满整个动态数组的状态值，取值范围为j: [1,len); i: [0,j)
	 * s_i 不等于 s_j ==> false;
	 * s_i 等于 s_j ==> i和j中间是否为空，为空则true;不为空，则取决于中间字符串是否为回文字符串的状态值；
	 * 更新maxLen和begin；
	 * 返回
	 * @param s
	 * @return
	 */
	public String longestPalindrome2(String s) {
		//特判
		if(s == null || s.length() == 0) return "";
		//初始化
		int maxLen = 1;
		int bengin = 0;
		int len = s.length();
		boolean[][] dp = new boolean[len][len];
		for(int i = 0; i < len; i ++){
			dp[i][i] = true;
		}
		//遍历
		char[] chars = s.toCharArray();
		for(int j = 1; j < len; j++){
			for(int i = 0; i < j; i++){
				//判断填充dp
				if(chars[i] != chars[j]){
					dp[i][j] = false;
				}else if(j - i == 1){
					dp[i][j] = true;
				}else{
					dp[i][j] = dp[i+1][j-1];
				}
				//更新maxLen和begin
				if(dp[i][j] && j-i+1 > maxLen){
					maxLen = j-i+1;
					bengin = i;
				}
			}
		}
		return s.substring(bengin,bengin + maxLen);
	}

	// P(i,j)P(i,j) 表示字符串 ss 的第 ii 到 jj 个字母组成的串（下文表示成 s[i:j]s[i:j]）是否为回文串
	public String longestPalindrome3(String s) {
		int n = s.length();
		boolean[][] dp = new boolean[n][n];
		String ans = "";
		for (int l = 0; l < n; ++l) {
			for (int i = 0; i + l < n; ++i) {
				int j = i + l;
				if (l == 0) {
					dp[i][j] = true;
				} else if (l == 1) {
					dp[i][j] = (s.charAt(i) == s.charAt(j));
				} else {
					dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
				}
				if (dp[i][j] && l + 1 > ans.length()) {
					ans = s.substring(i, i + l + 1);
				}
			}
		}
		return ans;
	}


}
